package main

import (
	"container/heap"
	"fmt"
	"math"
	"sort"
	"strconv"
	"strings"
)

func main() {
	fmt.Println("hello world!")
}

func GetNumberOfK(data []int, k int) int {
	// write code here
	if len(data) < 1 {
		return 0
	}
	i := 0
	j := len(data) - 1
	for i < j && j > 0 && i < len(data) {
		shouldContinue := false
		if data[i] < k {
			i++
			shouldContinue = true
		}
		if data[j] > k {
			j--
			shouldContinue = true
		}
		if !shouldContinue {
			break
		}
	}
	if j != i {
		return j - (i - 1)
	}
	return 0

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func TreeDepth(pRoot *TreeNode) int {
	// write code here
	height := 0
	if pRoot == nil {
		return height
	}
	return treeHeight(height, pRoot)
}

func treeHeight(height int, node *TreeNode) int {
	if node == nil {
		return height
	}
	height++
	leftHeight := treeHeight(height, node.Left)
	rightHeight := treeHeight(height, node.Right)
	if leftHeight > rightHeight {
		return leftHeight
	}
	return rightHeight
}

var balanced = true

func IsBalanced_Solution(pRoot *TreeNode) bool {
	// write code here
	if pRoot == nil {
		return true
	}
	l, h := foundHighestLoweast(pRoot, 0)
	return h-l <= 1 && balanced
}

func foundHighestLoweast(node *TreeNode, height int) (l, h int) {
	if node == nil {
		return height, height
	}
	height++
	leftL, leftH := foundHighestLoweast(node.Left, height)
	if leftH-leftL > 1 {
		balanced = false
	}
	rightL, rightH := foundHighestLoweast(node.Right, height)

	if rightH-rightL > 1 {
		balanced = false
	}
	if leftL < rightL {
		l = leftL
	} else {
		l = rightL
	}

	if leftH < rightH {
		h = rightH
	} else {
		h = leftH
	}
	return
}

func FindContinuousSequence(sum int) [][]int {
	// write code here
	if sum == 0 {
		return nil
	}
	i, j := 1, 1
	var result [][]int
	var item []int
	var tempSum int
	for i <= j && j < sum/2 {
		if tempSum < sum {
			j++
			tempSum += j
			continue
		}
		if tempSum > sum {
			tempSum -= i
			i++
			continue
		}
		for k := i; k <= j; k++ {
			item = append(item, k)
		}
		result = append(result, item)
		item = nil
		tempSum -= i
		i++
	}
	return result
}

//  2,8,9,10,14,16 19
func FindNumbersWithSum(array []int, sum int) []int {
	if len(array) == 0 {
		return nil
	}

	if array[0]*2 > sum {
		return nil
	}

	if array[len(array)-1]*2 < sum {
		return nil
	}
	var min int
	var minArray []int
	for l, r := 0, len(array)-1; l < r; {
		if array[l]+array[r] < sum {
			l++
			continue
		}
		if array[l]+array[r] > sum {
			r--
			continue
		}

		if minArray == nil {
			minArray = append(minArray, array[l], array[r])
			min = array[l] * array[r]
			continue
		}
		if array[l]*array[r] < min {
			minArray = append(minArray, array[l], array[r])
			min = array[l] * array[r]
			continue
		}
		l++

	}

	return minArray
}

func LeftRotateString(str string, n int) string {
	if len(str) == 0 {
		return str
	}
	n = n % len(str)
	bytes := ([]byte)(str)
	var result []byte
	result = append(result, bytes[n:]...)
	result = append(result, bytes[:n]...)
	return string(result)
}

func ReverseSentence(str string) string {
	s := strings.Split(str, " ")
	last := len(s) - 1
	for i := 0; i < len(s)/2; i++ {
		s[last-i], s[i] = s[i], s[last-i]
	}
	return strings.Join(s, " ")
}

var counted map[string]struct{} = make(map[string]struct{})

func movingCount(threshold int, rows int, cols int) int {
	search(threshold, 0, 0, rows, cols)
	result := len(counted)
	counted = make(map[string]struct{})
	return result
}

func search(threshold int, rowsLocation int, colsLocation int, rows int, cols int) {
	// 右、下
	if rowsLocation < rows && colsLocation < cols {
		// 判断是否已经走过
		if _, ok := counted[strconv.Itoa(rowsLocation)+":"+strconv.Itoa(colsLocation)]; !ok {
			// rlSplitStr := strings.Split(strconv.Itoa(rowsLocation), "")
			// clSplitStr := strings.Split(strconv.Itoa(colsLocation), "")

			var lengthThreshold int
			for i := rowsLocation; i > 0; {
				lengthThreshold += (i % 10)
				i = i / 10
			}

			for i := colsLocation; i > 0; {
				lengthThreshold += (i % 10)
				i = i / 10
			}
			// rlSplitStr := strings.Split(strconv.Itoa(rowsLocation), "")
			// clSplitStr := strings.Split(strconv.Itoa(colsLocation), "")

			// var lengthThreshold int
			// for _, v := range rlSplitStr {
			//  i, _ := strconv.Atoi(v)
			//  lengthThreshold += i
			// }

			// for _, v := range clSplitStr {
			//  i, _ := strconv.Atoi(v)
			//  lengthThreshold += i
			// }
			if lengthThreshold <= threshold {
				// 记录
				counted[strconv.Itoa(rowsLocation)+":"+strconv.Itoa(colsLocation)] = struct{}{}
				search(threshold, rowsLocation+1, colsLocation, rows, cols) // 下
				search(threshold, rowsLocation, colsLocation+1, rows, cols) // 右
			}
		}
	}
}

// o(n^2)
func maxInWindows1(num []int, size int) []int {
	// write code here
	if size < 1 {
		return nil
	}
	if size > len(num) {
		return nil
	}

	var maxs []int
	i, j := 0, size-1
	for j < len(num) {
		var max = num[i]
		for m := i + 1; m <= j; m++ {
			if num[m] > max {
				max = num[m]
			}
		}
		maxs = append(maxs, max)
		j++
		i++
	}
	return maxs
}

// o(n)
func maxInWindows(nums []int, k int) []int {
	queue := []int{}
	res := []int{}
	for i := 0; i < len(nums); i++ {
		for len(queue) > 0 && queue[len(queue)-1] < nums[i] {
			queue = queue[:len(queue)-1]
		}
		queue = append(queue, nums[i])
		if i >= k && queue[0] == nums[i-k] {
			queue = queue[1:]
		}
		if i >= k-1 {
			res = append(res, queue[0])
		}
	}
	return res
}

var a []int

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool  { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

func maxSlidingWindow(nums []int, k int) []int {
	a = nums
	q := &hp{make([]int, k)}
	for i := 0; i < k; i++ {
		q.IntSlice[i] = i
	}
	heap.Init(q)

	n := len(nums)
	ans := make([]int, 1, n-k+1)
	ans[0] = nums[q.IntSlice[0]]
	for i := k; i < n; i++ {
		heap.Push(q, i)
		for q.IntSlice[0] <= i-k {
			heap.Pop(q)
		}
		ans = append(ans, nums[q.IntSlice[0]])
	}
	return ans
}

/**
 *
 * @param pRoot TreeNode类
 * @param k int整型
 * @return TreeNode类
 */
var kthNode *TreeNode

func KthNode(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil {
		return nil
	}
	searchKthNode(pRoot, &k)
	return kthNode
}

func searchKthNode(node *TreeNode, k *int) {
	if node == nil || *k <= 0 {
		return
	}
	searchKthNode(node.Left, k)
	*k--
	if *k == 0 {
		kthNode = node
		return
	}
	searchKthNode(node.Right, k)
}

func isSymmetrical(pRoot *TreeNode) bool {
	if pRoot == nil {
		return true
	}
	var array []*TreeNode
	array = append(array, pRoot)
	var height int
	var shouldContinue bool = true
	var start_i, end_i int
	for shouldContinue {
		end_i = start_i + int(math.Pow(2, float64(height)))
		i := end_i
		shouldContinue = false
		for start_i < end_i {
			node := array[start_i]
			if node == nil {
				array = append(array, nil)
				array = append(array, nil)
			} else {
				shouldContinue = true
				array = append(array, array[start_i].Left)
				array = append(array, array[start_i].Right)
			}
			start_i++
		}
		// 判断
		// 1001
		height++
		end_i = start_i + int(math.Pow(2, float64(height)))
		for i < end_i-1 {

			if array[i] == nil && array[end_i-1] != nil ||
				array[end_i-1] == nil && array[i] != nil {
				return false
			}
			if array[i] != nil && array[end_i-1] != nil && array[i].Val != array[end_i-1].Val {
				return false
			}
			end_i--
			i++
		}
	}

	return true
}
